public class test09 {
    class Solution {
        public void solveSudoku(char[][] board) {
            backTracking(board);
        }
        private boolean backTracking(char[][] board){
            for(int row = 0;row<9;row++){
                for(int col = 0;col<9;col++){
                    if(board[row][col]!='.'){
                        continue;
                    }else{
                        for(char k = '1';k<='9';k++){
                            if(isValid(board,row,col,k)){
                                board[row][col] = k;
                                if(backTracking(board)){
                                    return true;
                                }
                                board[row][col] = '.';
                            }
                        }
                        return false;
                    }
                }
            }
            return true;
        }
        private boolean isValid(char[][] board,int row,int col,char k){
            //检查行：列变，行不变
            for(int i = 0;i<9;i++){
                if(board[row][i]==k){
                    return false;
                }
            }
            //检查列
            for(int i = 0;i<9;i++){
                if(board[i][col]==k){
                    return false;
                }
            }
            //检查3x3
            int startRow = (row/3)*3;
            int startCol = (col/3)*3;
            for(int i = startRow;i<=startRow+2;i++){
                for(int j = startCol;j<=startCol+2;j++){
                    if(board[i][j]==k){
                        return false;
                    }
                }
            }
            return true;
        }
    }
}
